//
// Created by 86131 on 2023/10/24.
//

#ifndef SHUJUJIEGUO_THREADED_BINARY_TREE_H
#define SHUJUJIEGUO_THREADED_BINARY_TREE_H
#include "BinaryTree.h"
//线索二叉树
class  Threaded_Binary_Tree:BinaryTree{
private:
    struct ThreadedNode : public BinaryTreeNode {
        bool isThreadedLeft;//是否有左子节点
        bool isThreadedRight;//是否有右子节点
        ThreadedNode(int value) : BinaryTreeNode(value), isThreadedLeft(false), isThreadedRight(false) {}
    };
public:
    Threaded_Binary_Tree(): BinaryTree() {}
    //线索化二叉树
    void threadTree() {
        BinaryTreeNode* prev = nullptr;//创建一个节点，用来保存节点的前驱节点
        threadTreeUtil(reinterpret_cast<ThreadedNode*>(root), prev);
    }
private:
    //创建一个函数，用来辅助递归线索化二叉树
    void threadTreeUtil(ThreadedNode* current, BinaryTreeNode* prev){
        if(current == nullptr)
            return;
        // 线索化左子树
        threadTreeUtil(static_cast<ThreadedNode*>(current->left), prev);
        //处理当前节点
        if(current->left== nullptr){
            current->left = prev;
            current->isThreadedLeft = true;
        }
        if(prev!= nullptr&&static_cast<ThreadedNode*>(prev)->right == nullptr){
            static_cast<ThreadedNode*>(prev)->right = current;
            static_cast<ThreadedNode*>(prev)->isThreadedRight = true;
        }
        prev = current;
        //线索化右子树
        threadTreeUtil(static_cast<ThreadedNode*>(current->right), prev);
    }
};
#endif //SHUJUJIEGUO_THREADED_BINARY_TREE_H
